package com.heima.leetcode.datastructure.binarytree;

import java.util.LinkedList;

/**
 * <strong>求二叉树的最大深度，leetcode中深度是从1计数的，深度理应考虑到叶子节点，104</strong>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/8 16:42
 */
public class MaxDepth {

    /**
     * <h3>方法一：递归</h3>
     * 求二叉树的最大深度
     * @param root 树的根节点
     * @return  树的深度
     */
    public static int maxDepth1(TreeNode root){
        // 递归结束条件：当前树为空
        if (root == null){
            return 0;
        }
        // 递的时候求找左子树的深度和右子树的深度
        int leftDepth = maxDepth1(root.left);
        int rightDepth = maxDepth1(root.right);
        // 留下左子树或右子树最大的深度
        return 1 + Math.max(leftDepth, rightDepth); // 和后序遍历一样的思想，处理左子树的深度，再处理右子树的深度，最后处理当前树的深度
    }

    /**
     * <h3>方法二：迭代（也就是非递归遍历（默认后序的来））</h3>
     * <h3>非递归遍历时用到的那个栈，其实在pop前记录的size就是一次从根节点某一个叶子节点的深度（从1计数），遍历从左向右嘛，最后就是让根节点与从左到右的叶子节点之间的距离进行比较，取出最大的，要注意的是如何限制叶子节点</h3>
     * 求二叉树的最大深度
     * @param root 树的根节点
     * @return 树的深度
     */
    public static int maxDepth2(TreeNode root){
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;
        TreeNode lastPop = null;
        int depth = 0;
        while (curr != null || !stack.isEmpty()){
            if (curr != null){
                stack.push(curr);
                curr = curr.left;
            }else {
                TreeNode last = stack.peek();
                if (last.right == null){
                    if (last.left == null && stack.size() > depth){ // 限制last为叶子节点，从根节点到该叶子节点的距离
                        depth = stack.size();
                    }
                    lastPop = stack.pop();
                }else if (last.right == lastPop){
                    lastPop = stack.pop();
                }else {
                    curr = last.right;
                }
            }
        }
        return depth;
    }

    /**
     * <h3>方法三：层序遍历，层数就是深度</h3>
     * @param root 树的根节点
     * @return 树的最大深度
     */
    @SuppressWarnings("all")
    public static int maxDepth3(TreeNode root){
        if (root == null){
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0; // 层数默认从1编号
        while (!queue.isEmpty()){
            int levelSize = queue.size();
            // 一轮for循环就是处理当前层x
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
            level++;
        }
        return level;
    }
}
